\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage[pdftex]{graphicx}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{hyperref}

\lstset{
language=MATLAB,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
}

\title{CS 5846 Decision Theory I: Assignment 4} 
\author{Yifan Tong (UG), yt347}
\date{December 02, 2010}

\begin{document} 
\maketitle 
\newpage
\section{Problem 1} % (fold)
\label{sec:problem_1}
\subsection{Part a}
Since $\emptyset$ is the empty set, by Axiom 2, $\forall f, g, h$,
\[f_{\emptyset}h = h\]
\[g_{\emptyset}h = h\]
Therefore,
\[f_\emptyset h\sim g_\emptyset h\]
\[f\sim_{\emptyset} g\]
Therefore, by definition, $\emptyset$ is null.
\subsection{Part b}
For any acts $f$ and $h$, if $A$ is null, then, by Axiom 2,
\[f_Bh = f_Bh_Ah\]
Similarly, given any act $g$,
\[g_Bh = g_Bh_Ah \]
Since $B\subseteq A$,
\[g_Bh_Ah \sim f_Bh_Ah\]
Therefore,
\[f_Bh \sim g_Bh\]
And therefore,
\[f\sim_Bh\]
Therefore, $B$ is null.
\subsection{Part c}
Given $A$ is null,
\[f\sim_A g\]
Therefore, for all $h$
\[f_Ah \sim_A g_Ah\]
Let $h = f_Bk$, we have
\[f_Af_Bk \sim g_Af_Bk\]
Similarly, given that $f\sim_B g$, and let $h=g_Ak$, we have,
\[f_Bg_Ak \sim g_Bg_Ak\]
By transitivity, we have
\[g_Af_Bk \sim f_Bg_Ak\]
Therefore, for all $k$,
\[f_Af_Bk \sim g_Bg_Ak\]
\[f\sim_{A\cup B} g\]
Therefore, by definition,  $A\cup B$ is null.
% section problem_1 (end)

\section{Problem 2} % (fold)
\label{sec:problem_2}
(Grad)
% section problem_2 (end)

\section{Problem 3} % (fold)
\label{sec:problem_3}
\subsection{Part a}
\begin{eqnarray*}
EU(d_1) &=& 0.5 \times (0.25 \times 0 + 0.75 \times  -8) + 0.5 \times (0.75 \times  0 + 0.25 \times -8)\\
&=& -4\\
EU(d_2) &=& 0.5 \times (0.25 \times -10 + 0.75 \times  0) + 0.5 \times (0.75 \times  -10 + 0.25 \times 0)\\
&=& -5\\
EU(d_3) &=& 0.5 \times (0.25 \times -4 + 0.75 \times  -3) + 0.5 \times (0.75 \times -4 + 0.25 \times -3)\\
&=& -3.5
\end{eqnarray*}
Assume the DM is a utility maximizer, the preferred choice is $d_3$.
\subsection{Part b}
\begin{eqnarray*}
Pr(s_1|\mbox{pre}=s_1) &=& Pr(\mbox{pre} = s_1\wedge \mbox{next} = s_1 | Pr(s_1) = \frac{3}{4}) + Pr(\mbox{pre} = s_1\wedge \mbox{next} = s_1 | Pr(s_1) =\frac{1}{4})\\
&=& \frac{5}{8}\\
Pr(s_2|\mbox{pre}=s_1) &=& 1 - Pr(s_1|\mbox{pre}=s_1)\\
&=& \frac{3}{8}
\end{eqnarray*}
With $p=(\frac{5}{8}, \frac{3}{8})$,
\begin{eqnarray*}
EU(d_1) &=& \frac{5}{8} \times 0 + \frac{3}{8} \times -8\\
&=& -3\\
EU(d_2) &=& \frac{5}{8} \times -10 + \frac{3}{8} \times 0\\
&=& -\frac{25}{4}\\
EU(d_3) &=& \frac{5}{8} \times -4 + \frac{3}{8} \times -3\\
&=& -\frac{29}{8}
\end{eqnarray*}
Assume the DM is a utility maximizer, the preferred choice is $d_1$.
\subsection{Part c}
\begin{eqnarray*}
Pr(s_1|\mbox{pre}=s_2) &=& Pr(\mbox{pre} = s_2\wedge \mbox{next} = s_1 | Pr(s_2) = \frac{1}{4}) + Pr(\mbox{pre} = s_2\wedge \mbox{next} = s_1 | Pr(s_2) =\frac{3}{4})\\
&=& \frac{3}{8}\\
Pr(s_2|\mbox{pre}=s_2) &=& 1 - Pr(s_1|\mbox{pre}=s_2)\\
&=& \frac{5}{8}
\end{eqnarray*}
With $p=(\frac{3}{8}, \frac{5}{8})$,
\begin{eqnarray*}
EU(d_1) &=& \frac{3}{8} \times 0 + \frac{5}{8} \times -8\\
&=& -5\\
EU(d_2) &=& \frac{3}{8} \times -10 + \frac{5}{8} \times 0\\
&=& -\frac{15}{4}\\
EU(d_3) &=& \frac{3}{8} \times -4 + \frac{5}{8} \times -3\\
&=& -\frac{27}{8}
\end{eqnarray*}
Assume the DM is a utility maximizer, the preferred choice is $d_3$.
\subsection{Part d}
\begin{eqnarray*}
\delta &=& EU_b(d_1) -EU_a(d_3) \\
&=& (-3) - (-3.5)\\
&=& 0.5
\end{eqnarray*}
Therefore, knowing the previous draw was $s_1$ is worth 0.5 utilities to the DM.
% section problem_3(end)
\section{Problem 4} % (fold)
\label{sec:problem_4}
\subsection{Part a}
Assume, without the loss of generality, utilities $u_0$ for \$0, $u_1$ for \$1,000,000, and $u_5$ for \$5,000,000.\\\\
We are given,
\begin{eqnarray*}
P_1 &=& (0.00, 1.00, 0.00)\\
P_2 &=& (0.01, 0.89, 0.10)\\
P_3 &=& (0.90, 0.00, 0.10)\\
P_4 &=& (0.89, 0.11, 0.00)
\end{eqnarray*}
Assume, $P = (1, 0, 0)$ and $\alpha = 0.5$; then, by the independence theorem,
\begin{eqnarray*}
P_1 &\succ& P_2\\
0.5 P_1 + 0.5 P &\succ& 0.5 P_2 + 0.5 P\\
0.5 (u_1) + 0.5 (u_0) &>& 0.5 ( 0.01 u_0 + 0.89 u_1 + 0.1 u_5) + 0.5 (u_0)\\
-0.01 u_0 + 0.11 u_1 - 0.1 u_5 &>& 0\\\\
P_3 &\succ& P_4\\
0.5 P_3 + 0.5 P &\succ& 0.5 P_4 + 0.5 P\\
0.5 (0.9 u_0 + 0.1u_5) + 0.5 (u_0) &>& 0.5 ( 0.89 u_0 + 0.11 u_1) + 0.5 (u_0)\\
-0.01 u_0 + 0.11 u_1 - 0.1 u_5 &<& 0
\end{eqnarray*}
We have a contradiction, and therefore, the Allais Paradox does not satisfy the vNM Independence Postulate.\\\\
It is important to note that, the same contradiction can be reached with any arbitrary $\alpha$ ($0<\alpha\leq 1$) and $P$, as both variables cancel out towards the last step.
\subsection{Part b}
Given the state space
\[S = \{R, B, Y\}\]
and the prize:
\[X = \{0, 100\}\]
We have lottery $a$:
\begin{eqnarray*}
a(R) = 100, 
a(B) = 0, 
a(Y) = 0
\end{eqnarray*}
and lottery $a'$:
\begin{eqnarray*}
a'(R) = 0, 
a'(B) = 100, 
a'(Y) = 0
\end{eqnarray*}
We have lottery $b$:
\begin{eqnarray*}
b(R) = 100, 
b(B) = 0, 
b(Y) = 100
\end{eqnarray*}
and lottery $b'$:
\begin{eqnarray*}
b'(R) = 0, 
b'(B) = 100, 
b'(Y) = 100
\end{eqnarray*}
Consider a new state space $T = \{R, B\}$, such that $S = T\cup \{Y\}$\\\\
On $T$, we have,
\begin{eqnarray*}
a &=& b\\
a' &=& b'
\end{eqnarray*}
Therefore, if $a\succ a'$, then by the independence postulate, we have $b \succ b'$.  However, the DM prefers $b'$ over $b$, and therefore, we have a contradiction.
% section problem_4(end)

\section{Problem 5} % (fold)
\label{sec:problem_5}
\subsection{Part a}
\subsubsection{Protocol 1}
If B/B, show a (random) Black side\\
If B/W, show Black\\
If W/W, show a (random) White side\\\\
Given the protocol, the probability of observing a black card is (B/W or B/B):
\[Pr(\mbox{black on table}) = \frac{2}{3}\]
Given that a black card is observed, the probability of the other side is black is (B/B):
\[Pr(\mbox{black on bottom}|\mbox{black on table}) =\frac{1}{2}\]
\subsubsection{Protocol 2}
If B/B, show a (random) Black size\\
If B/W, show White\\
If W/W, show a (random) White side\\\\
Given the protocol, there is only one way of observing a black card on the table (B/B), and therefore, if a black card is observed, the probability of the other side being black is 100\%.
\subsection{Part b}
If Bob does not know Alice's protocol, a good way to model the problem is with principle of uncertainty.  We make a few reasonable assumptions with regards to Alice's protocol:
\begin{enumerate}
\item Alice must place a card (with one side facing up) on the table.
\item The two sides of B/B and W/W cards are indistinguishable.
\item When Alice picks the B/W card, she chooses a side to show at random, without any bias.
\end{enumerate}
Under these assumptions, Alice shows a black back 50\% of the time.

% section problem_5 (end)

\section{Problem 6} % (fold)
\label{sec:problem_6}
\subsection{Part a}
\subsubsection{Not studying causes poor performance}
Given
\begin{eqnarray*}
Pr(W | S ) &=& 0.8\\
Pr(W | \neg S) &=& 0.1
\end{eqnarray*}
where $W =$ doing well, and $S =$ study.\\\\
The causal probabilities are trivial:
\begin{eqnarray*}
Pr(W | S ) &=& 0.8\\
Pr(\neg W | S) &=& 0.2\\
Pr(W | \neg S ) &=& 0.1\\
Pr(\neg W | \neg S) &=& 0.9
\end{eqnarray*}
\subsubsection{Not sleeping causes not studying and not doing well}
Given
\begin{eqnarray*}
Pr(W | S ) &=& Pr(W \wedge S | P) + Pr(W \wedge S | \neg P) = 0.8\\
Pr(W | \neg S) &=& Pr(W\wedge\neg S| P) + Pr(W\wedge\neg S | \neg P) = 0.1
\end{eqnarray*}
where $W =$ doing well, $S =$ study, and $P = $ sleep.\\\\
Assume the following probabilities (arbitrarily)
\begin{eqnarray*}
Pr(P) &=& 0.6\\
Pr(\neg P) &=& 0.4\\
Pr(W \wedge S | P) &=& 0.6\\
Pr(W \wedge S | \neg P) &=& 0.2\\
Pr(W\wedge\neg S| P)&=& 0.07\\
Pr(W\wedge\neg S | \neg P) &=& 0.03
\end{eqnarray*}
The causal probability between $W$ and $S$ remain the same:
\begin{eqnarray*}
Pr(W | S ) &=& 0.8\\
Pr(W | \neg S ) &=& 0.1
\end{eqnarray*}
Note that, based on the description of the scenario, $S$, $W$, and $P$ have the following relationship:
\begin{center}
\includegraphics[scale=0.6]{bn1.png}
\end{center}
Let,
\begin{eqnarray*}
Pr(A) &=& Pr(W \wedge S| P)+Pr(W \wedge \neg S| P)\\
Pr(B) &=& Pr(W \wedge S|\neg P)+Pr(W \wedge \neg S|\neg P)
\end{eqnarray*}
The probability of doing well \textbf{caused by} sleeping, independent of studying, is:
\begin{eqnarray*}
Pr(P \mbox{ causes }W) &=& Pr(A)\times Pr(P)+ Pr(B)\times Pr(\neg P)\\
&=& 0.67 \times 0.6 + 0.23 \times 0.4\\
&=& 0.494
\end{eqnarray*}
\subsection{Part b}
\subsubsection{$S\rightarrow W$}
\begin{eqnarray*}
EU(Study) &=& Pr(W|S)\times 4 + Pr(\neg W| S) \times -1\\
&=& 0.8 \times 4 + 0.1 \times (-1)\\
&=& 3.1
\end{eqnarray*}
\subsubsection{$P\rightarrow S, W$}
\begin{eqnarray*}
EU(Study) &=& 0.494 \times 4 + 0.506 \times (-1)\\
&=& 1.47
\end{eqnarray*}
\subsection{Part c}
In order to distinguish the two models, we must know which model is (more) correct.  Meaning that, we need to look for signs that show either studying causes good performance, or sleeping causes good performance.  Statistical data and statistical analyses are needed to provide concrete proof as to which causal model correctly describes the relationship.
% section problem_6 (end)

\section{Problem 7} % (fold)
\label{sec:problem_7}
\subsection{Part a}
\begin{eqnarray*}
Pr(\neg B \cap C | A ) &=& Pr( \neg B | A ) \times Pr(C | A)\\
&=& 0.2 \times 0.4\\
&=& 0.08
\end{eqnarray*}
\subsection{Part b}
\begin{eqnarray*}
Pr(A | B \cap \neg C ) &=& Pr( B \cap \neg C |A)\\
&=&Pr( B | A ) \times Pr(\neg C | A)\\
&=& 0.8 \times 0.6\\
&=& 0.48
\end{eqnarray*}
\subsection{Part c}
\subsubsection{i}
The following has to hold:
\[I_{Pr}(X, \mbox{NonDes}_G(X) | \mbox{Par}_G(X)\]
More specifically,
\begin{enumerate}
\item I$(d, a | b, c)$
\item I$(b, c| a)$
\item I$(c, b | a)$
\end{enumerate}
\subsubsection{ii}
Yes.  For the Bayesian network to represent Pr, it must satisfy the following condition:
\[I_{Pr}(X, \mbox{NonDes}_G(X) | \mbox{Par}_G(X)\]
$A$ is a non-descendant of $D$, and $C$ is a parent of $D$; therefore, $A$ is conditionally independent of $D$ given $C$.
\subsubsection{iii}
Yes.  Similar to above, $C$ is a non-descendant of $B$, and $A$ is a parent of $B$; therefore, $C$ is conditionally independent of $B$ given $A$.
% section problem_7 (end)
\end{document}